//给定 M×N 矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。 
//
// 示例： 
//
// 现有矩阵 matrix 如下： 
//
// 
//[
//  [1,   4,  7, 11, 15],
//  [2,   5,  8, 12, 19],
//  [3,   6,  9, 16, 22],
//  [10, 13, 14, 17, 24],
//  [18, 21, 23, 26, 30]
//]
// 
//
// 给定 target = 5，返回 true。 
//
// 给定 target = 20，返回 false。 
//
// Related Topics 数组 二分查找 分治 矩阵 👍 68 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-02 00:27:05
 * @description 面试题 10.09.排序矩阵查找
 */
public class SortedMatrixSearchLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SortedMatrixSearchLcci fun=new SortedMatrixSearchLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // omlogn
    public boolean searchMatrix1(int[][] matrix, int target) {
		if(matrix.length==0||matrix[0].length==0) return false;
		int i=0,j=matrix[0].length-1;
		while (i<matrix.length&&j>=0){
			if(matrix[i][j]==target) return true;
			if(matrix[i][j]>target) j--;
			else i++;
		}
		return false;
    }
	public boolean searchMatrix(int[][] matrix, int target) {
		if (matrix.length == 0 || matrix[0].length == 0) {
			return false;
		}
		for (int[] row : matrix) {
			int index = search(row, target);
			if (index >= 0) {
				return true;
			}
		}
		return false;
	}
	// o(m+n)  对每一行二分
	public int search(int[] nums, int target) {
		int low = 0, high = nums.length - 1;
		while (low <= high) {
			int mid = (high - low) / 2 + low;
			int num = nums[mid];
			if (num == target) {
				return mid;
			} else if (num > target) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return -1;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
